
import java.util.ArrayList;
import java.util.List;
// https://leetcode.cn/problems/path-sum-ii
public class PathSum {
    private  class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            List<List<Integer>> res = new ArrayList<>();
            if(root == null) return res;
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            search(root,targetSum-root.val,list,res);
            return res;

        }

        private void search(TreeNode node , int sum , List<Integer> path , List<List<Integer>> res)
        {
            if(sum == 0 && node.left == null && node.right == null)
            {
                List<Integer> tmp = new ArrayList<>(path);
                res.add(tmp);
            }
            if(node.left != null)
            {
                path.add(node.left.val);
                search(node.left,sum-node.left.val,path,res);
                path.remove(path.size()-1);
            }
            if(node.right != null)
            {
                path.add(node.right.val);
                search(node.right,sum-node.right.val,path,res);
                path.remove(path.size()-1);
            }
        }
    }
}
